package src.backtracking_algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author starsea
 * @date 2024-08-19 11:04
 */

public class Test04 {
    public static void main(String[] args) {
        int[] arr={1,2,3};
        int c=combinationSum4(arr,4);

    }
    static List<List<Integer>>ret;
    static List<Integer> path;
    static int tar;
    static int sum;
    static int ans;
    public static int combinationSum4(int[] nums, int target) {
        ret=new ArrayList<>();
        path=new ArrayList<>();
        tar=target;
        ans=0;
        sum=0;
        dfs(nums);
        return ans;
    }
    public static void dfs(int[] nums)
    {
        if(sum>=tar)
        {
            if(sum==tar)
            {
                ans++;
            }
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(sum<tar)
            {
                sum+=nums[i];
                dfs(nums);
                sum-=nums[i];
            }
        }
    }
}
